#include <cstdlib>
#include <iostream>
#include <string>
using std::cout;
using std::endl;

template <typename T> struct Node {
    T value;
    Node* next;
    Node(const T& value) : value(value), next(nullptr) {}
};

template <typename T> 
class KsoString 
{
  private:
    Node<T>* head; // 链表头指针
    int size;

  public:
    KsoString() : head(nullptr), size(0) {}

    //元素个数
    int len() const { return size; }

    //追加结点
    void push_back(const T& val) 
    {
        Node<T>* newNode = new Node<T>(val);
        if (head == nullptr)
            head = newNode;
        else {
            Node<T>* p;
            for (p = head; p->next != nullptr; p = p->next)
                ;
            p->next = newNode;
        }
        size++;
    }

    //删除下标为index的结点,形参index取值从0~len-1
    void del(int index = 0) 
    {
       if (index == 0) //删除头结点
        {
            Node<T>* p = head;
            head = p->next;
            delete p;
            size--;
        } 
        else 
        { //找到要删除的节点前一个节点
            Node<T>* p = head;
            for (int i = 0; i < index - 1; ++i)
                p = p->next;

            Node<T>* pnext = p->next;
            p->next = pnext->next;
            delete pnext;
            size--;
        }
        if (size == 0)
            head = nullptr;
    }

    //在下标为index处插入val,形参index取值从0~len
    void insert(T val, int index = 0) 
    {
        Node<T>* newNode = new Node<T>(val);
        if (index == 0) //插入头结点
        {
            newNode->next = head;
            head = newNode;
        } 
        else 
        {
            Node<T>* p = head;
            //找到要插入节点前一个节点
            for (int i = 0; i < index - 1; i++)
                p = p->next;
            newNode->next = p->next;
            p->next = newNode;
        }
        size++;
    }

    T operator[](int index) 
    {
        Node<T>* p = head;
        for (int i = 0; i < index; i++)
            p = p->next;
        return p->value;
    }

    void print() 
    {
        for (Node<T>* p = head; p != nullptr; p = p->next)
            cout << p->value;
        cout << endl;
    }
};

int main() 
{
    KsoString<char> str1;
    str1.push_back('L');
    str1.push_back('u');
    str1.push_back('c');
    str1.push_back('k');
    str1.push_back('y');
    cout << "========str1===========" << endl;
    str1.print();
    cout << "str1[2] = " << str1[2] << endl;
    cout << "========after str1.del(3);===========" << endl;
    str1.del(3);
    str1.print();
    cout << "========after str1.insert('x',0);===========" << endl;
    str1.insert('x', 0);
    str1.print();

    KsoString<wchar_t> str2;
    str2.push_back(L'你');
    str2.push_back(L'好');
    str1.push_back('e');
    std::wcout.imbue(std::locale(""));
    cout << "========wchar str2==================" << endl;
    str2.print();

    return 0;
}